package com.atguigu.tree;

import java.util.Arrays;

/**
 * 堆排序算法
 */
public class HeapSortDemo {

    public static void main(String[] args) {
        int arr[] = {5,3,4,6,8};

        //生成了一个大顶堆二叉树,从下往上执行
        for (int i = arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,5);
        }


        for (int j=0;j<arr.length-1;j++){
            int temp = arr[arr.length-1-j];
            arr[arr.length-1-j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,arr.length-1-j);
        }

        System.out.println(Arrays.toString(arr));

    }

    /**
     *
     * @param arr 要转换的数组
     * @param i 要调整的子树根节点位置,找到整个i包括它下面的子树最大值，所以它下面子树都要调整
     * @param length 数组的长度
     */
    public static void adjustHeap(int arr[],int i,int length){

        int temp = arr[i];


        for (int k = i*2+1;k<length;k=k*2+1){
            //找到左右子树最大的那个节点
            if(k+1<length && arr[k] < arr[k+1]){
                k++;
            }

            if (arr[k] > temp){
                arr[i] = arr[k];
                i = k;
            }else {
                break;  //因为是从下往上调整，下面的子树已经是调整好的了，
                // 之所以循环，是为了上方子树调整以后，下面可能还要重排序
            }


        }

        arr[i] = temp;

    }
}
